Skip to main content
4:30 pm
>> it is often said that mathematics is a universal language. no matter where we are or who we are, regardless of culture, country, gender, race, or even religion, certain mathematical principles remain true.
4:31 pm
for example, 100 can always be reduced to its basic building blocks of 2's and 5's no matter what language it is that we speak every day. mathematics is indeed a language common to all of us on planet earth, and the most fundamental letters of its alphabet are called "the primes." these numbers have the very unique quality of being divisible by only themselves and one. they can't be factored any further, and as a result, they're often called the "atoms of arithmetic." prime numbers are so fundamental and mysterious that they've intrigued human mathematicians for thousands of years. are they so fundamental that other intelligent beings in the universe might know about them, too? in the 1960s, seti suggested that if there are other intelligent beings out there, they might share the language of mathematics with us. seti relied on the idea that math is so fundamental to how we
4:32 pm
describe the physical universe that other beings might see the universe through the same lens. and if we shared this common language of mathematics, then the prime numbers, those atoms of arithmetic, might be used as a basis of interstellar communication. and in 1974, at the arecibo radio telescope in puerto rico, astronomer frank drake beamed a message into outer space. the message consisted of 1,679 binary digits. drake chose 1,679 because it's a semiprime, the product of two prime numbers, that can only be broken down into 23 and 73. drake arranged the bits in such a way that, when viewed as a rectangle of 73 rows and 23 columns, it would read as a pictogram that included the numbers 1 through 10, the dna double helix, and the earth's solar system. on earth, at least, we use math to explain everything from microscopic dna to the mysteries of outer space.
4:33 pm
and while it's a language that might connect us to intelligent life from another galaxy someday in the future, today it certainly connects us to each other across cultures and continents, and even to our ancestors from the past. now, this is a replica of the ishango bone, which originated in central africa some 20,000 years ago, and it's thought to be one of mankind's first tally sticks, a simple device used for counting. in its use of notches to stand in for objects or instances, it becomes one of the first examples of abstract thinking. but even more, the columns of asymmetrically grouped notches suggest that early humans had a mathematical understanding that went beyond mere counting. the notches on both the left and right columns are all odd numbers: 9, 11, 13, 17, 19, and 21. the numbers on each of those columns add up to 60, and the numbers in the central column add up to 48. now, 60 and 48 are both multiples of 12, perhaps indicating an understanding of
4:34 pm
multiplication and division. but perhaps more intriguing is the fact that the numbers on the left column are all primes. twenty thousand years ago, someone may have recognized these numbers for their uniqueness. did early humans know what made the primes special? now, most historians agree that ancient cultures seemed to appreciate numbers for their utility in things like commerce, agriculture, and calendars. but the idea that numbers could be interesting in and of themselves seems to be something that emerged relatively late, some 18,000 years after the ishango bone, with classical greek civilization. scholars like pythagoras, aristotle, and euclid, they were the first "pure" mathematicians, who, beginning around the 7th century b.c., began to explore numbers for their own sake. in fact, the word "mathematics" comes from the greek mathema, which means "learning." and the word "calculation" is from the greek khalix, meaning "pebble," and from that we get "calculus."
4:35 pm
some of the greeks' most complex and abstract explorations began with something as simple and tangible as a handful of pebbles. any whole number can be represented by a corresponding quantity of pebbles. and one way in which the greeks classified numbers was according to the shapes that could be produced with their pebble-pile equivalents. for example, if a number of pebbles could be arranged in a square, that number was called a "square." thus, with the sides being equal, a number times itself, as we know, is said to be "squared." three rows of three pebbles, 3 x 3, equaling 9. that's not a bad example. so most numbers, even if they couldn't be shaped into squares, could at least be represented by rectangles, where by "rectangle" we mean only those that have more than one pebble in each dimension. for example, take the number 12. it can be represented by rectangles that are either two rows of six pebbles or three rows of four pebbles, so that
4:36 pm
the height and width of these boxes actually give us a visualization of a basic multiplication problem. since a rectangle has length and width, the number of its pebbles represents both the rectangle itself and the answer to a multiplication problem such as 3 x 4. but notice that certain quantities of pebbles just don't fit in a box. if you're trying to make one of these so-called "fat" rectangles out of a number like 11 or 13, something is always left over. so a number like 11 or 13 can never be the answer to a multiplication problem other than 1 x itself. this ends up being true for many numbers: 2, 3, 5, 7, 11, 13, 17, 19, on and on it goes. today we call these numbers prime numbers. and like any kind of surprising discovery, be it a strange kind of bird or a flickering star in the sky, once it's identified, it needs to be investigated. so it was euclid, the man that
4:37 pm
most of us think of as the father of geometry, who first recorded the properties of the primes. his investigation of the primes begins with what we call the "fundamental theorem of arithmetic," and this states that every natural number greater than 1 can be written as a unique product of prime numbers. we call these prime numbers its prime factors. for example, 12 is the product of 4 x 3. and this can be further reduced to the prime factors of... likewise, a number like 1,200 is the product 3 x 16 x 25, and this can then be further reduced to... thus, the fundamental theorem of arithmetic establishes the importance of prime numbers as the basic building blocks of any positive integer. this is why we call them the atoms of arithmetic. so then euclid goes one step further. and that's the point. having identified the primes, we can now ask questions like, how
4:38 pm
many of them are there? and what euclid proved is that there are an infinite number. so let's see how he did it. euclid's proof of the infinitude of primes shows that if we multiply together any finite collection of primes and then add 1, the resulting sum is not divisible by any of the primes that we start with. for example, multiply the prime numbers 2, 3, and 5 and then add 1. the result is 31, a number which can't be divided by either 2, 3, or 5. but in fact, 31 is itself prime, so we've discovered a new prime number! now, if we continue down this path and use the primes 2, 3, 5, and 31 to create a new number, this time we get 931, which also cannot be factored by any of the primes we used to create it. as it turns out, 931 is not a prime. it can be divided by both 7 and 19. but guess what, we've just discovered two new primes. so even if the output of
4:39 pm
euclid's formula is not itself a prime number, any of its factors must be new primes. now, you might notice, however, that euclid's method doesn't give us prime numbers in the order that we'd expect. in this example, it skipped over the primes 11, 13, and 17. but his method does show us that out of any list of primes that we use to make a number by euclid's method, there's always another waiting to be found. consequently, the list of primes must go on forever. there must be an infinitude of prime numbers, each one larger than the next. if we keep repeating euclid's method, multiplying all the primes that we have at any point and then adding 1 and then looking for new primes, we always end up with these kinds of gaps. 7,919 turns out to be the 1,000th prime number. and here's a prime that appears much later down the number line. but what about those skipped numbers? euclid's proof of the infinitude of primes doesn't provide a systematic way of finding all the prime numbers. but 100 years after euclid,
4:40 pm
another greek mathematician, eratosthenes, tried to find one. eratosthenes designed a simple algorithm -- that is, a set of well-defined instructions or a kind of mathematical recipe -- that sifts out composite numbers from prime numbers. it came to be called the "sieve of eratosthenes," and here's how it works: suppose we wanted to find all the primes less than or equal to 100. so beginning with 2, we work our way through the numbers in the following fashion. we keep the first prime that we encounter, 2, and then delete every multiple of 2 in the list: 4, 6, 8, 10, 12, and so on. they all disappear. then we go back to the beginning of the list. the first number that wasn't deleted is 3, and it's a prime number. and then we work through the list again, this time deleting all the multiples of 3. then we go back to the beginning, and the first one we see is 5, also a prime, not divisible by either 2 or 3.
4:41 pm
so using this process, all but the primes are eliminated and you have discovered every prime in the list up to 100. but remember, there are an infinite number of primes. and the sieve of eratosthenes is a pretty tedious and time-consuming way of finding them. is there a better way? could there be a formula that produces prime numbers? that's the sort of thing mathematicians love to play with: are there better ways to do things, formulas to make things, to play with ideas, twist and turn the numbers around, looking for patterns that might lead to an understanding of something as mysterious as the primes. so, what if we played with a pretty simple pattern like the "doubling numbers," powers of 2: 2, 4, 8, 16, 32, and so on. these aren't primes, but could we do a slight change to turn them into a prime, like maybe subtracting 1 from each? well, let's take a look. if we do that, we see that a lot of the resulting numbers that we get are in fact primes. i'm not the first person to
4:42 pm
figure this out. years ago, in 1644, a french monk named marin mersenne was following this very path when he noticed the same thing. mersenne suspected that the formula...would often yield a prime number, maybe even infinitely often, but he wasn't sure. and in fact, we are still finding larger and larger what we call "mersenne primes" today using his formula. so, now, the formula for a mersenne prime is so beautiful, but the numbers grow so quickly that in fact there are hundreds of mathematicians out there these days searching for mersenne prime numbers. g.i.m.p.s., the "great internet mersenne prime search," is a bunch of, well, prime hunters that link together thousands of computers all around the world working to find larger and larger mersenne primes. but by the year 2006, nearly four centuries after mersenne, only 44 had been found.
4:43 pm
the 44th mersenne prime, discovered by two mathematicians at the university of central missouri, is... it has 9,808,358 digits. this is a number even larger than the number of atoms in the universe. and it's in discoveries like this, and in the ongoing pursuit of even larger mersenne primes -- or perhaps proving that no such larger primes exist -- that we find the joy, the fun, and the beauty of mathematics. it is truly the one pursuit where it makes sense and is perhaps even required to take your explorations out into the infinite, where no one has gone before. and so mathematics offers the explorer a kind of freedom, bound only by the laws of logic. we can pose our own puzzles or take on those puzzles posed by the world around us. whether large or small, each unsolved puzzle or problem is
4:44 pm
like a new mountain to be scaled, a sea to be crossed, or a new frontier to be explored. now, there's that 44th mersenne prime again. it's amazing that although we may have been aware of the primes for 20,000 years, so much about them remains unresolved. patterns have been observed, but we can't be sure the patterns continue on the number line out into infinity. we found the 44th mersenne prime, but we don't even know if it's the last one or if the pattern goes on forever. what's more, the mersenne prime is just one kind of pattern we can find. now, take a look at the first few primes. we see several examples of "twin primes," pairs of primes that are just two units apart: 3 and 5, 5 and 7, 11 and 13. and now we go farther and farther: 827 and 829, 1,607 and 1,609, and so on and so on... maybe. is there an infinite number of
4:45 pm
twin primes? that question was posed by euclid 2,300 years ago, and to this day still, no one has been able to either prove or disprove his twin prime conjecture. an infinite number of primes, perhaps an infinite number of twin primes. small primes, huge primes. short gaps between primes, some very long gaps between primes. the apparent lack of rhyme or reason to the spacing and location of primes is just the kind of puzzle that fuels a mathematician's curiosity. in particular, the primes were of deep interest to one of the greatest mathematicians of all time, carl friedrich gauss. born in 1777, itself a prime number, gauss was a child prodigy who, at an early age, calculated lists of primes into the millions. gauss, by the way, also proposed using mathematics to communicate with extraterrestrials. but he considered prime numbers to be of the highest significance and wrote, "the dignity of the science itself seems to require that every
4:46 pm
possible means be explored for the solution of a problem so elegant and so celebrated." gauss would be the first person to see that the seemingly unpredictable occurrences of the primes actually had a beautiful and succinct description. so a modern-day mathematician who can help us figure out what gauss was getting at is our own terry tao. so terry is a professor of mathematics at ucla, a recent recipient of the fields medal, which is mathematics' highest honor, and also a recipient of a macarthur genius award. so, and in fact, gauss, who was called the "prince of mathematics," well, terry's not a prince, but he has been called the "mozart of math." so, terry, thanks for coming and helping us learn about prime numbers. >> thanks, though it's funny i'm called mozart, because i'm terrible at the piano. >> so, terry, i know that the primes are a deep and abiding interest of yours, and i think they are for a lot of people because on the one hand they seem like they just occur
4:47 pm
arbitrarily as we go along the number lines. so in the beginning they're sort of closely spaced, and then as we start whizzing down to the end of the number line, in fact they're farther and farther and farther apart. and it would seem like they might not be able to be explained at all. but in fact we know that there is structure there, right? >> right. so we can't predict individual primes very well, like if you have a sequence of primes whizzing by, we don't know whether the next number's going to be prime or not prime very easily, but in aggregate, you look at statistics of the primes. if you look at how many primes there are up to some number, like up to 1 million, even though it's hard to tell which of those numbers is prime, we can actually count, in aggregate, a pattern emerges. >> the idea of using statistics is in fact -- or probability, so to speak -- is an old one and goes back to gauss. he was actually able to show that if you start to graph how many primes do we have up to a point. so how many primes are there less than 100 or less than 1,000 and so on and so forth, that you get this, as we see here, this jaggedy -- what we call a "step
4:48 pm
function," estimating the number of primes. but on the other hand, when we step back, then what happens? >> right, well, then the curving was much more continuous. in fact, it converges to a very exact and beautiful curve given by the natural logarithm function. >> and gauss -- gauss predicted this, but in fact he didn't prove it. >> no, that had to wait until about 200 years later, i think, to be proven. >> so this very smooth curve is now sort of canonized in what's called the "prime number theorem," but in fact we now know today that it doesn't quite go far enough. it's an estimate, but you could do better, and doing better was what was in the mind of a student who was at the same university where gauss was teaching, bernhard riemann. is that right? >> yes, yes. so riemann studied the area between the jagged function, which counts the primes, and this smooth curve. >> that's right, so the smooth curve again is some approximation, but the actual number, it's not getting right generally. >> right, it's either above -- overshoots or undershoots, and so there's this funny area that you have to understand.
4:49 pm
and what riemann -- the great idea basically of viewing this funny wave, kind of like a sound wave, looking for like -- like frequencies, or musical notes, if you will, in this -- in this sound. and the sound is what's called "the music of the primes." >> your work is actually finding what i think most people would recognize as real patterns in the primes. it's related to the notion of twin primes. >> right, so twin primes are a very simple kind of pattern in the primes, primes that are just a distance of two apart, and we still can't even find those. but working with ben green, we were able to find -- to prove that there were these other type of patterns in the primes, these arithmetic progressions. >> so that's primes that are just regularly spaced. >> right, so a sequence of primes where, yeah, the spacing between each prime and the previous one is the same. yeah, and so, what we were able to show is that we can find progressions, arithmetic progressions, in the primes of arbitrary length. so you give me any number, like 100, somewhere in the primes
4:50 pm
there will be an arithmetic progression of 100 primes where each prime -- the distance between each prime and the previous one is exactly the same. i can't tell you what the spacing is, i can't tell you where the progression is, but i know that somewhere out there, there is a progression of primes. in fact, there are infinitely many progressions of primes of any given length. it's like if you want to demonstrate that a box is -- there's something in a box, you can open it and look at it or you can weigh it and compare that to the weight of an empty box. and if it's larger, you know that there's something in the box, but it doesn't tell you what it is, how to find it. so that's kind of what we do. >> exactly. so this was a totally outstanding result, and what was it like to be working on a hard problem? when you started off, did you say, "this is the problem i want to tackle; it's a hard problem and i want to tackle it"? >> well, it's a problem that everyone knew about, and so there's a lot of much simpler problems related to that problem. so mathematics is kind of like climbing a cliff: there are these really high points that you want to get to so you can enjoy the view, but there's a
4:51 pm
lot of sort of much lower places you have to get to first. and so we didn't try to do this problem initially; we were working on much simpler things. >> you just wanted to take a short hike initially. >> at some point we made this breakthrough and we discovered that this path which could keep going up and up, that it could actually attack this problem. and once we realized that, we sort of dropped everything else and we worked on that for six months, and everything sort of came together very nicely. and all the things that we've been working on semi-related, it all came together. so it was actually very satisfying. >> this has been a lot of fun, so thanks a lot. >> okay, thank you very much. >> some 20,000 years since the ishango bone and now 2,300 years since euclid, the pursuit of the primes has not ended. number theory in general and the study of the primes in particular has often been seen and continues to be seen as the canonical example of pure mathematics, math for math's sake. in other words, done for no other reason than to climb the mountain.
4:52 pm
but still, the search has resulted in some practical applications, like encryption. >> my job focuses on protecting you. encryption is a way of mangling data so that it's recoverable if you know a secret. the problems i work on vary a lot. sometimes i do cryptography-type stuff, where i'm looking at a very specific attack and analyzing it from every possible angle, every possible variant to see if there's any circumstances under which that attack will cause a problem. a lot of private data is sent on the internet: credit card numbers, bank numbers, social security numbers. any of that which got out would allow the bad guys to do identity theft, cause a lot of trouble, and can lose you a lot of money. i'm ray perlner, i work at the information technology laboratory at n.i.s.t., the national institute of standards and technology. n.i.s.t. has been setting standards in cryptography for
4:53 pm
over 25 years. so here is the crypto lab, and in here we do a variety of software testing on both encryption standards and operating systems and anything else that might be security-sensitive. here is an antique from 1980, older than i am. this implements the n.i.s.t. data encryption algorithm. we don't need this machine because any desktop pc can do the work that this used to do. because the algorithm implemented by this machine is a secret-key algorithm, in order to use it, you need sender and recipient to share a secret, which in general is not true of any two computers that you pick randomly communicating using the internet. this is where public-key cryptography comes in. public-key cryptography is a product of prime numbers, n=pq. in addition to n will be a public exponent, e. with public-key algorithms, only
4:54 pm
the recipient needs to know a secret, and the recipient just needs to securely get the public key, which explains to the sender how to encrypt data so only the recipient can read it. e can be set pretty much to anything as long as it doesn't divide p-1 or q-1. 3 is a common choice, 17 is common, 65,537 also very common. primes are itant because the two hard problems that are the basis for all public-key cryptography are the discrete logarithm problem and integer factorization. integer factorization is just where you take a large number that's a product of two large primes and figure out what the two primes are without having prior knowledge of that. if you can figure out what those two primes are, you've broken the algorithm. in order for the bad guy, given only the public key and possibly some signed messages or matched
4:55 pm
pairs of plain text and cipher text, the bad guy should only be able to factor the number if he's capable of doing 2-to-the-80th operations, which is approximately a trillion trillion operations. that is considered infeasible. it's been some of the most interesting work i've ever been involved in. lots of problem-solving. it's exciting to me because you take a look at these problems, and first looking at them, you have no clue where they're going to lead, and then you have some kind of an insight, and suddenly it all makes sense. >> can we expect that codes based on prime numbers might be routinely broken in the future as technology and our understanding of the primes advances? or have such encryptions already been broken by someone out there? assuming that such intelligent life exists, are prime numbers indeed so fundamental that other life forms would understand
4:56 pm
them? some scientists argue that humans and extraterrestrials might be so different that their biology, culture, history, and even sciences would provide no basis for communication. while we use math to describe the universe, their models of reality might differ drastically from ours. what if they don't count? what if, to them, prime numbers are simply the color blue? but to us humans, mathematics is a common language, fundamental to how we describe the world around us. with it, mathematicians are unlocking the secrets, breaking the codes of the cosmos. yet in many ways, prime numbers -- the very building blocks of this mathematical language, those atoms of arithmetic -- remain as mysterious to us as the farthest galaxy. which makes mathematicians the real explorers of the universe...on a journey that began 20,000 years ago and will never end.
4:57 pm
captions by lns captioning portland, oregon
4:58 pm
4:59 pm
disc Borrow a DVD of this show
info Stream Only
Uploaded by
TV Archive
on 1/24/2013